/**
 * Copyright (C) 2014-2019 by Wen Yu.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 * <p>
 * Any modifications to this file must keep this entire header intact.
 * <p>
 * Change History - most recent changes go on top of previous changes
 * <p>
 * ArrayUtils.java
 * <p>
 * Who   Date       Description
 * ====  =========  ======================================================================
 * WY    14Jun2015  Bug fix for toNBits() to use long data type internally
 * WY    04Jun2015  Rewrote all concatenation related methods
 * WY    02Jun2015  Bug fix for generic concatenate methods
 * WY    06Apr2015  Added reverse(byte[]) to reverse byte array elements
 * WY    06Jan2015  Added reverse() to reverse array elements
 * WY    10Dec2014  Moved reverseBits() from IMGUtils to here along with BIT_REVERSE_TABLE
 * WY    08Dec2014  Fixed bug for flipEndian() with more than 32 bit sample data
 * WY    07Dec2014  Changed method names for byte array to other array types conversion
 * WY    07Dec2014  Added new methods to work with floating point TIFF images
 * WY    03Dec2014  Added byteArrayToFloatArray() and byteArrayToDoubleArray()
 * WY    25Nov2014  Added removeDuplicates() to sort and remove duplicates from int arrays
 * WY    12Nov2014  Changed the argument sequence for flipEndian()
 * WY    11Nov2014  Changed flipEndian() to include scan line stride to skip bits
 * WY    11Nov2014  Added toNBits() to convert byte array to nBits data unit
 * WY    28Oct2014  Added flipEndian() to work with TIFTweaker mergeTiffImagesEx()
 */

package com.symaster.common.util;

import java.lang.reflect.Array;
import java.nio.*;
import java.util.*;
import java.util.stream.Collectors;

/**
 * Array utility class
 *
 * @author Wen Yu, yuwen_66@yahoo.com
 * @version 1.0 09/18/2012
 */
public class ArrayUtils {
    // Bit mask 0 - 32 bits (inclusive)
    private static final int[] MASK = {0x000,
            0x1, 0x3, 0x7, 0xf,
            0x1f, 0x3f, 0x7f, 0xff,
            0x1ff, 0x3ff, 0x7ff, 0xfff,
            0x1fff, 0x3fff, 0x7fff, 0xffff,
            0x1ffff, 0x3ffff, 0x7ffff, 0xfffff,
            0x1fffff, 0x3fffff, 0x7fffff, 0xffffff,
            0x1ffffff, 0x3ffffff, 0x7ffffff, 0xfffffff,
            0x1fffffff, 0x3fffffff, 0x7fffffff, 0xffffffff // 32 bits
    };

    // Bit reverse table to work with TIFF FillOrder field.
    private static final byte[] BIT_REVERSE_TABLE = {
            (byte) 0x00, (byte) 0x80, (byte) 0x40, (byte) 0xc0, (byte) 0x20, (byte) 0xa0, (byte) 0x60, (byte) 0xe0,
            (byte) 0x10, (byte) 0x90, (byte) 0x50, (byte) 0xd0, (byte) 0x30, (byte) 0xb0, (byte) 0x70, (byte) 0xf0,
            (byte) 0x08, (byte) 0x88, (byte) 0x48, (byte) 0xc8, (byte) 0x28, (byte) 0xa8, (byte) 0x68, (byte) 0xe8,
            (byte) 0x18, (byte) 0x98, (byte) 0x58, (byte) 0xd8, (byte) 0x38, (byte) 0xb8, (byte) 0x78, (byte) 0xf8,
            (byte) 0x04, (byte) 0x84, (byte) 0x44, (byte) 0xc4, (byte) 0x24, (byte) 0xa4, (byte) 0x64, (byte) 0xe4,
            (byte) 0x14, (byte) 0x94, (byte) 0x54, (byte) 0xd4, (byte) 0x34, (byte) 0xb4, (byte) 0x74, (byte) 0xf4,
            (byte) 0x0c, (byte) 0x8c, (byte) 0x4c, (byte) 0xcc, (byte) 0x2c, (byte) 0xac, (byte) 0x6c, (byte) 0xec,
            (byte) 0x1c, (byte) 0x9c, (byte) 0x5c, (byte) 0xdc, (byte) 0x3c, (byte) 0xbc, (byte) 0x7c, (byte) 0xfc,
            (byte) 0x02, (byte) 0x82, (byte) 0x42, (byte) 0xc2, (byte) 0x22, (byte) 0xa2, (byte) 0x62, (byte) 0xe2,
            (byte) 0x12, (byte) 0x92, (byte) 0x52, (byte) 0xd2, (byte) 0x32, (byte) 0xb2, (byte) 0x72, (byte) 0xf2,
            (byte) 0x0a, (byte) 0x8a, (byte) 0x4a, (byte) 0xca, (byte) 0x2a, (byte) 0xaa, (byte) 0x6a, (byte) 0xea,
            (byte) 0x1a, (byte) 0x9a, (byte) 0x5a, (byte) 0xda, (byte) 0x3a, (byte) 0xba, (byte) 0x7a, (byte) 0xfa,
            (byte) 0x06, (byte) 0x86, (byte) 0x46, (byte) 0xc6, (byte) 0x26, (byte) 0xa6, (byte) 0x66, (byte) 0xe6,
            (byte) 0x16, (byte) 0x96, (byte) 0x56, (byte) 0xd6, (byte) 0x36, (byte) 0xb6, (byte) 0x76, (byte) 0xf6,
            (byte) 0x0e, (byte) 0x8e, (byte) 0x4e, (byte) 0xce, (byte) 0x2e, (byte) 0xae, (byte) 0x6e, (byte) 0xee,
            (byte) 0x1e, (byte) 0x9e, (byte) 0x5e, (byte) 0xde, (byte) 0x3e, (byte) 0xbe, (byte) 0x7e, (byte) 0xfe,
            (byte) 0x01, (byte) 0x81, (byte) 0x41, (byte) 0xc1, (byte) 0x21, (byte) 0xa1, (byte) 0x61, (byte) 0xe1,
            (byte) 0x11, (byte) 0x91, (byte) 0x51, (byte) 0xd1, (byte) 0x31, (byte) 0xb1, (byte) 0x71, (byte) 0xf1,
            (byte) 0x09, (byte) 0x89, (byte) 0x49, (byte) 0xc9, (byte) 0x29, (byte) 0xa9, (byte) 0x69, (byte) 0xe9,
            (byte) 0x19, (byte) 0x99, (byte) 0x59, (byte) 0xd9, (byte) 0x39, (byte) 0xb9, (byte) 0x79, (byte) 0xf9,
            (byte) 0x05, (byte) 0x85, (byte) 0x45, (byte) 0xc5, (byte) 0x25, (byte) 0xa5, (byte) 0x65, (byte) 0xe5,
            (byte) 0x15, (byte) 0x95, (byte) 0x55, (byte) 0xd5, (byte) 0x35, (byte) 0xb5, (byte) 0x75, (byte) 0xf5,
            (byte) 0x0d, (byte) 0x8d, (byte) 0x4d, (byte) 0xcd, (byte) 0x2d, (byte) 0xad, (byte) 0x6d, (byte) 0xed,
            (byte) 0x1d, (byte) 0x9d, (byte) 0x5d, (byte) 0xdd, (byte) 0x3d, (byte) 0xbd, (byte) 0x7d, (byte) 0xfd,
            (byte) 0x03, (byte) 0x83, (byte) 0x43, (byte) 0xc3, (byte) 0x23, (byte) 0xa3, (byte) 0x63, (byte) 0xe3,
            (byte) 0x13, (byte) 0x93, (byte) 0x53, (byte) 0xd3, (byte) 0x33, (byte) 0xb3, (byte) 0x73, (byte) 0xf3,
            (byte) 0x0b, (byte) 0x8b, (byte) 0x4b, (byte) 0xcb, (byte) 0x2b, (byte) 0xab, (byte) 0x6b, (byte) 0xeb,
            (byte) 0x1b, (byte) 0x9b, (byte) 0x5b, (byte) 0xdb, (byte) 0x3b, (byte) 0xbb, (byte) 0x7b, (byte) 0xfb,
            (byte) 0x07, (byte) 0x87, (byte) 0x47, (byte) 0xc7, (byte) 0x27, (byte) 0xa7, (byte) 0x67, (byte) 0xe7,
            (byte) 0x17, (byte) 0x97, (byte) 0x57, (byte) 0xd7, (byte) 0x37, (byte) 0xb7, (byte) 0x77, (byte) 0xf7,
            (byte) 0x0f, (byte) 0x8f, (byte) 0x4f, (byte) 0xcf, (byte) 0x2f, (byte) 0xaf, (byte) 0x6f, (byte) 0xef,
            (byte) 0x1f, (byte) 0x9f, (byte) 0x5f, (byte) 0xdf, (byte) 0x3f, (byte) 0xbf, (byte) 0x7f, (byte) 0xff
    };

    private ArrayUtils() {
    } // Prevents instantiation

    // From Effective Java 2nd Edition.
    public static List<Integer> asList(final int[] a) {
        if (a == null) {
            throw new NullPointerException();
        }
        return new AbstractList<Integer>() {// Concrete implementation built atop skeletal implementation
            public Integer get(int i) {
                return a[i];
            }

            @Override
            public Integer set(int i, Integer val) {
                int oldVal = a[i];
                a[i] = val;
                return oldVal;
            }

            public int size() {
                return a.length;
            }
        };
    }

    public static void bubbleSort(int[] array) {
        int n = array.length;
        boolean doMore = true;

        while (doMore) {
            n--;
            doMore = false;  // assume this is our last pass over the array

            for (int i = 0; i < n; i++) {
                if (array[i] > array[i + 1]) {
                    // exchange elements
                    int temp = array[i];
                    array[i] = array[i + 1];
                    array[i + 1] = temp;
                    doMore = true;  // after an exchange, must look again
                }
            }
        }
    }

    public static <T extends Comparable<? super T>> void bubbleSort(T[] array) {
        int n = array.length;
        boolean doMore = true;

        while (doMore) {
            n--;
            doMore = false;  // assume this is our last pass over the array

            for (int i = 0; i < n; i++) {
                if (array[i].compareTo(array[i + 1]) > 0) {
                    // exchange elements
                    T temp = array[i];
                    array[i] = array[i + 1];
                    array[i + 1] = temp;
                    doMore = true;  // after an exchange, must look again
                }
            }
        }
    }

    /**
     * Since Set doesn't allow duplicates add() return false
     * if we try to add duplicates into Set and this property
     * can be used to check if array contains duplicates.
     *
     * @param input input array
     * @return true if input array contains duplicates, otherwise false.
     */
    public static <T> boolean checkDuplicate(T[] input) {
        Set<T> tempSet = new HashSet<T>();

        for (T str : input) {
            if (!tempSet.add(str)) {
                return true;
            }
        }

        return false;
    }

    public static byte[] concat(byte[] first, byte[]... rest) {
        if (first == null) {
            throw new IllegalArgumentException("Firt element is null");
        }
        if (rest.length == 0) {
            return first;
        }
        // Now the real stuff
        int totalLength = first.length;

        for (byte[] array : rest) {
            totalLength += array.length;
        }

        byte[] result = new byte[totalLength];

        int offset = first.length;

        System.arraycopy(first, 0, result, 0, offset);

        for (byte[] array : rest) {
            System.arraycopy(array, 0, result, offset, array.length);
            offset += array.length;
        }

        return result;
    }

    /**
     * Type safe concatenation of arrays with upper type bound T
     * <p>
     * Note: if type parameter is not explicitly supplied, it will be inferred as the
     * upper bound for the two parameters.
     *
     * @param arrays the arrays to be concatenated
     * @return a concatenation of the input arrays
     * @throws NullPointerException if any of the input array is null
     */
    public static <T> T[] concat(T[]... arrays) {
        if (arrays.length == 0) {
            throw new IllegalArgumentException("Varargs length is zero");
        }

        if (arrays.length == 1) {
            return arrays[0];
        }

        // Now the real stuff
        int totalLength = 0;
        // Taking advantage of the compiler type inference
        Class<?> returnType = arrays.getClass().getComponentType().getComponentType();

        for (T[] array : arrays)
            totalLength += array.length;

        @SuppressWarnings("unchecked")
        T[] result = (T[]) Array.newInstance(returnType, totalLength);

        int offset = 0;
        for (T[] array : arrays) {
            System.arraycopy(array, 0, result, offset, array.length);
            offset += array.length;
        }

        return result;
    }

    /**
     * Type safe concatenation of arrays with upper type bound T
     *
     * @param type   type bound for the concatenated array
     * @param arrays arrays to be concatenated
     * @return a concatenation of the arrays.
     * @throws NullPointerException if any of the arrays to be
     *                              concatenated is null.
     */
    public static <T> T[] concat(Class<T> type, T[]... arrays) {
        if (type == null) {
            throw new IllegalArgumentException("Input type class is null");
        }

        if (arrays.length == 0) { // Return a zero length array instead of null
            @SuppressWarnings("unchecked")
            T[] result = (T[]) Array.newInstance(type, 0);

            return result;
        }

        // Make sure we have at least two arrays to concatenate
        if (arrays.length == 1) {
            return arrays[0];
        }

        int totalLength = 0;
        for (T[] array : arrays)
            totalLength += array.length;

        @SuppressWarnings("unchecked")
        T[] result = (T[]) Array.newInstance(type, totalLength);

        int offset = 0;
        for (T[] array : arrays) {
            System.arraycopy(array, 0, result, offset, array.length);
            offset += array.length;
        }

        return result;
    }

    public static int findEqualOrLess(int[] a, int key) {
        return findEqualOrLess(a, 0, a.length, key);
    }

    /**
     * Find the index of the element which is equal or less than the key.
     * The array must be sorted in ascending order.
     *
     * @param a   the array to be searched
     * @param key the value to be searched for
     * @return index of the search key or index of the element which is closest to but less than the search key or
     * -1 is the search key is less than the first element of the array.
     */

    public static int findEqualOrLess(int[] a, int fromIndex, int toIndex, int key) {
        int index = Arrays.binarySearch(a, fromIndex, toIndex, key);

        // -index - 1 is the insertion point if not found, so -index - 1 -1 is the less position
        if (index < 0) {
            index = -index - 1 - 1;
        }

        // The index of the element which is either equal or less than the key
        return index;
    }

    public static <T> int findEqualOrLess(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c) {
        int index = Arrays.binarySearch(a, fromIndex, toIndex, key, c);

        // -index - 1 is the insertion point if not found
        if (index < 0) {
            index = -index - 1 - 1;
        }

        return index;
    }

    public static <T> int findEqualOrLess(T[] a, T key, Comparator<? super T> c) {
        return findEqualOrLess(a, 0, a.length, key, c);
    }

    /**
     * Flip the endian of the input byte-compacted array
     *
     * @param input          the input byte array which is byte compacted
     * @param offset         the offset to start the reading input
     * @param len            number of bytes to read
     * @param bits           number of bits for the data before compaction
     * @param scanLineStride scan line stride to skip bits
     * @param bigEndian      whether or not the input data is in big endian order
     * @return a byte array with the endian flipped
     */
    public static byte[] flipEndian(byte[] input, int offset, int len, int bits, int scanLineStride, boolean bigEndian) {
        long value = 0;
        int bits_remain = 0;
        long temp_byte = 0; // Must make this long, otherwise will give wrong result for bits > 32
        int empty_bits = 8;

        byte[] output = new byte[input.length];

        int strideCounter = 0;

        int end = offset + len;
        int bufIndex = 0;

        int temp = bits;
        boolean bigEndianOut = !bigEndian;

        loop:
        while (true) {

            if (!bigEndian) {
                value = (temp_byte >> (8 - bits_remain));
            } else {
                value = (temp_byte & MASK[bits_remain]);
            }

            while (bits > bits_remain) {
                if (offset >= end) {
                    break loop;
                }

                temp_byte = input[offset++] & 0xff;

                if (bigEndian) {
                    value = ((value << 8) | temp_byte);
                } else {
                    value |= (temp_byte << bits_remain);
                }

                bits_remain += 8;
            }

            bits_remain -= bits;

            if (bigEndian) {
                value = (value >> bits_remain);
            }

            // Write bits bit length value in opposite endian
            if (bigEndianOut) {
                temp = bits - empty_bits;
                output[bufIndex] |= ((value >> temp) & MASK[empty_bits]);

                while (temp > 8) {
                    output[++bufIndex] |= ((value >> (temp - 8)) & MASK[8]);
                    temp -= 8;
                }

                if (temp > 0) {
                    output[++bufIndex] |= ((value & MASK[temp]) << (8 - temp));
                    temp -= 8;
                }
            } else { // Little endian
                temp = bits;
                output[bufIndex] |= ((value & MASK[empty_bits]) << (8 - empty_bits));
                value >>= empty_bits;
                temp -= empty_bits;
                // If the code is longer than the empty_bits
                while (temp > 8) {
                    output[++bufIndex] |= (value & 0xff);
                    value >>= 8;
                    temp -= 8;
                }

                if (temp > 0) {
                    output[++bufIndex] |= (value & MASK[temp]);
                    temp -= 8;
                }
            }

            empty_bits = -temp;

            if (++strideCounter % scanLineStride == 0) {
                empty_bits = 0;
                bits_remain = 0;
            }
        }

        return output;
    }

    // From http://stackoverflow.com/questions/6162651/half-precision-floating-point-in-java
    // returns all higher 16 bits as 0 for all results
    public static int fromFloat(float fval) {
        int fbits = Float.floatToIntBits(fval);
        int sign = fbits >>> 16 & 0x8000; // sign only
        int val = (fbits & 0x7fffffff) + 0x1000; // rounded value

        if (val >= 0x47800000) // might be or become NaN/Inf
        {                     // avoid Inf due to rounding
            if ((fbits & 0x7fffffff) >= 0x47800000) {                        // is or must become NaN/Inf
                if (val < 0x7f800000) // was value but too large
                {
                    return sign | 0x7c00;  // make it +/-Inf
                }
                return sign | 0x7c00 |  // remains +/-Inf or NaN
                        (fbits & 0x007fffff) >>> 13; // keep NaN (and Inf) bits
            }
            return sign | 0x7bff;  // unrounded not quite Inf
        }
        if (val >= 0x38800000)  // remains normalized value
        {
            return sign | val - 0x38000000 >>> 13; // exp - 127 + 15
        }
        if (val < 0x33000000) // too small for subnormal
        {
            return sign;     // becomes +/-0
        }
        val = (fbits & 0x7fffffff) >>> 23;  // tmp exp for subnormal calc
        return sign | ((fbits & 0x7fffff | 0x800000) // add subnormal bit
                + (0x800000 >>> val - 102) // round depending on cut off
                >>> 126 - val); // div by 2^(1-(exp-127+15)) and >> 13 | exp=0
    }

    /**
     * Since nonzero-length array is always mutable, we should return
     * a clone of the underlying array as BIT_REVERSE_TABLE.clone().
     *
     * @return the byte reverse table.
     */
    public static byte[] getBitReverseTable() {
        return BIT_REVERSE_TABLE.clone();
    }

    // Insertion sort
    public static void insertionsort(int[] array) {
        insertionsort(array, 0, array.length - 1);
    }

    public static void insertionsort(int[] array, int start, int end) {
        int j;

        for (int i = start + 1; i < end + 1; i++) {

            int temp = array[i];
            for (j = i; j > start && temp <= array[j - 1]; j--)
                array[j] = array[j - 1];
            // Move temp to the right place
            array[j] = temp;
        }
    }

    // Insertion sort
    public static <T extends Comparable<? super T>> void insertionsort(T[] array) {
        insertionsort(array, 0, array.length - 1);
    }

    // Insertion sort
    public static <T extends Comparable<? super T>> void insertionsort(T[] array, int start, int end) {
        int j;

        for (int i = start + 1; i < end + 1; i++) {
            T temp = array[i];
            for (j = i; j > start && temp.compareTo(array[j - 1]) <= 0; j--)
                array[j] = array[j - 1];
            // Move temp to the right place
            array[j] = temp;
        }
    }

    // Merge sort
    public static void mergesort(int[] array) {
        mergesort(array, new int[array.length], 0, array.length - 1);
    }

    public static void mergesort(int[] array, int left, int right) {
        if (left < 0 || right > array.length - 1) {
            throw new IllegalArgumentException("Array index out of bounds");
        }
        mergesort(array, new int[array.length], left, right);
    }

    private static void mergesort(int[] array, int[] temp, int left, int right) {
        // check the base case
        if (left < right) {
            // Get the index of the element which is in the middle
            int middle = left + (right - left) / 2;
            // Sort the left side of the array
            mergesort(array, temp, left, middle);
            // Sort the right side of the array
            mergesort(array, temp, middle + 1, right);
            // Merge the left and the right
            merge(array, temp, left, middle, right);
        }
    }

    public static <T extends Comparable<? super T>> void mergesort(T[] array) {
        mergesort(array, 0, array.length - 1);
    }

    public static <T extends Comparable<? super T>> void mergesort(T[] array, int left, int right) {
        if (left < 0 || right > array.length - 1) {
            throw new IllegalArgumentException("Array index out of bounds");
        }
        @SuppressWarnings("unchecked")
        T[] temp = (T[]) Array.newInstance(array.getClass().getComponentType(), array.length);
        mergesort(array, temp, left, right);
    }

    // Merge sort
    private static <T extends Comparable<? super T>> void mergesort(T[] array, T[] temp, int left, int right) {
        // check the base case
        if (left < right) {
            // Get the index of the element which is in the middle
            int middle = left + (right - left) / 2;
            // Sort the left side of the array
            mergesort(array, temp, left, middle);
            // Sort the right side of the array
            mergesort(array, temp, middle + 1, right);
            // Merge the left and the right
            merge(array, temp, left, middle, right);
        }
    }

    private static <T extends Comparable<? super T>> void merge(T[] array, T[] temp, int left, int middle, int right) {
        // Copy both parts into the temporary array
        for (int i = left; i <= right; i++) {
            temp[i] = array[i];
        }
        int i = left;
        int j = middle + 1;
        int k = left;
        while (i <= middle && j <= right) {
            if (temp[i].compareTo(temp[j]) <= 0) {
                array[k] = temp[i];
                i++;
            } else {
                array[k] = temp[j];
                j++;
            }
            k++;
        }
        while (i <= middle) {
            array[k] = temp[i];
            k++;
            i++;
        }
    }

    private static void merge(int[] array, int[] temp, int left, int middle, int right) {
        // Copy both parts into the temporary array
        for (int i = left; i <= right; i++) {
            temp[i] = array[i];
        }
        int i = left;
        int j = middle + 1;
        int k = left;
        while (i <= middle && j <= right) {
            if (temp[i] <= temp[j]) {
                array[k] = temp[i];
                i++;
            } else {
                array[k] = temp[j];
                j++;
            }
            k++;
        }
        while (i <= middle) {
            array[k] = temp[i];
            k++;
            i++;
        }
    }

    /**
     * Packs all or part of the input byte array which uses "bits" bits to use all 8 bits.
     *
     * @param input input byte array
     * @param start offset of the input array to start packing
     * @param bits  number of bits used by the input array
     * @param len   number of bytes from the input to be packed
     * @return the packed byte array
     */
    public static byte[] packByteArray(byte[] input, int start, int bits, int len) {
        //
        if (bits == 8) {
            return ArrayUtils.subArray(input, start, len);
        }
        if (bits > 8 || bits <= 0) {
            throw new IllegalArgumentException("Invalid value of bits: " + bits);
        }

        byte[] packedBytes = new byte[(bits * len + 7) >> 3];
        short[] mask = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};

        int index = 0;
        int empty_bits = 8;
        int end = start + len;

        for (int i = start; i < end; i++) {
            // If we have enough space for input byte, one step operation
            if (empty_bits >= bits) {
                packedBytes[index] |= ((input[i] & mask[bits]) << (empty_bits - bits));
                empty_bits -= bits;
                if (empty_bits == 0) {
                    index++;
                    empty_bits = 8;
                }
            } else { // Otherwise two step operation
                packedBytes[index++] |= ((input[i] >> (bits - empty_bits)) & mask[empty_bits]);
                packedBytes[index] |= ((input[i] & mask[bits - empty_bits]) << (8 - bits + empty_bits));
                empty_bits += (8 - bits);
            }
        }

        return packedBytes;
    }

    /**
     * Packs all or part of the input byte array which uses "bits" bits to use all 8 bits.
     * <p>
     * We assume len is a multiplication of stride. The parameter stride controls the packing
     * unit length and different units <b>DO NOT</b> share same byte. This happens when packing
     * image data where each scan line <b>MUST</b> start at byte boundary like TIFF.
     *
     * @param input  input byte array to be packed
     * @param stride length of packing unit
     * @param start  offset of the input array to start packing
     * @param bits   number of bits used in each byte of the input
     * @param len    number of input bytes to be packed
     * @return the packed byte array
     */
    public static byte[] packByteArray(byte[] input, int stride, int start, int bits, int len) {
        //
        if (bits == 8) {
            return ArrayUtils.subArray(input, start, len);
        }
        if (bits > 8 || bits <= 0) {
            throw new IllegalArgumentException("Invalid value of bits: " + bits);
        }

        int bitsPerStride = bits * stride;
        int numOfStrides = len / stride;
        byte[] packedBytes = new byte[((bitsPerStride + 7) >> 3) * numOfStrides];
        short[] mask = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};

        int index = 0;
        int empty_bits = 8;
        int end = start + len;
        int strideCounter = 0;

        for (int i = start; i < end; i++) {
            // If we have enough space for input byte, one step operation
            if (empty_bits >= bits) {
                packedBytes[index] |= ((input[i] & mask[bits]) << (empty_bits - bits));
                empty_bits -= bits;
            } else { // Otherwise, split the pixel between two bytes.
                // This will never happen for 1, 2, 4, 8 bits color depth image
                packedBytes[index++] |= ((input[i] >> (bits - empty_bits)) & mask[empty_bits]);
                packedBytes[index] |= ((input[i] & mask[bits - empty_bits]) << (8 - bits + empty_bits));
                empty_bits += (8 - bits);
            }
            // Check to see if we need to move to next byte
            if (++strideCounter % stride == 0 || empty_bits == 0) {
                index++;
                empty_bits = 8;
            }
        }

        return packedBytes;
    }

    // Quick sort
    public static void quicksort(int[] array) {
        quicksort(array, 0, array.length - 1);
    }

    public static void quicksort(int[] array, int start, int end) {
        int inner = start;
        int outer = end;
        int mid = (start + end) / 2;

        do {
            // work in from the start until we find a swap to the
            // other partition is needed
            while ((inner < mid) && (array[inner] <= array[mid]))
                inner++;

            // work in from the end until we find a swap to the
            // other partition is needed

            while ((outer > mid) && (array[outer] >= array[mid]))
                outer--;

            // if inner index <= outer index, swap elements
            if (inner < mid && outer > mid) {
                swap(array, inner, outer);
                inner++;
                outer--;
            } else if (inner < mid) {
                swap(array, inner, mid - 1);
                swap(array, mid, mid - 1);
                mid--;
            } else if (outer > mid) {
                swap(array, outer, mid + 1);
                swap(array, mid, mid + 1);
                mid++;
            }
        } while (inner != outer);

        // recursion
        if ((mid - 1) > start) {
            quicksort(array, start, mid - 1);
        }
        if (end > (mid + 1)) {
            quicksort(array, mid + 1, end);
        }
    }

    // Quick sort
    public static <T extends Comparable<? super T>> void quicksort(T[] array) {
        quicksort(array, 0, array.length - 1);
    }

    // Based on java2novice.com example

    // Quick sort
    public static <T extends Comparable<? super T>> void quicksort(T[] array, int low, int high) {
        int i = low, j = high;
        // Get the pivot element from the middle of the list
        T pivot = array[low + (high - low) / 2];

        // Divide into two lists
        while (i <= j) {
            // If the current value from the left list is smaller then the pivot
            // element then get the next element from the left list
            while (array[i].compareTo(pivot) < 0) {
                i++;
            }
            // If the current value from the right list is larger then the pivot
            // element then get the next element from the right list
            while (array[j].compareTo(pivot) > 0) {
                j--;
            }

            // If we have found a values in the left list which is larger then
            // the pivot element and if we have found a value in the right list
            // which is smaller then the pivot element then we exchange the
            // values.
            // As we are done we can increase i and j
            if (i <= j) {
                swap(array, i, j);
                i++;
                j--;
            }
        }
        // Recursion
        if (low < j) {
            quicksort(array, low, j);
        }
        if (i < high) {
            quicksort(array, i, high);
        }
    }

    /**
     * Remove duplicate elements from an int array
     *
     * @param input input unsorted int array
     * @return a sorted int array with unique elements
     */
    public static int[] removeDuplicates(int[] input) {
        // return if the array length is less than 2
        if (input.length < 2) {
            return input;
        }

        // Sort the array first
        Arrays.sort(input);

        int j = 0;
        int i = 1;

        while (i < input.length) {
            if (input[i] == input[j]) {
                i++;
            } else {
                input[++j] = input[i++];
            }
        }

        int[] output = new int[j + 1];

        System.arraycopy(input, 0, output, 0, j + 1);

        return output;
    }

    // Reverse the bit order (bit sex) of a byte array
    public static void reverseBits(byte[] input) {
        for (int i = input.length - 1; i >= 0; i--)
            input[i] = BIT_REVERSE_TABLE[input[i] & 0xff];
    }

    public static byte[] reverse(byte[] array) {
        if (array == null) {
            throw new IllegalArgumentException("Input array is null");
        }
        int left = 0;
        int right = array.length - 1;
        byte tmp;
        while (left < right) {
            tmp = array[right];
            array[right] = array[left];
            array[left] = tmp;
            left++;
            right--;
        }

        return array;
    }

    // Reverse the array
    public static <T> void reverse(T[] data) {
        for (int left = 0, right = data.length - 1; left < right; left++, right--) {
            T temp = data[left];
            data[left] = data[right];
            data[right] = temp;
        }
    }

    // Shell sort
    public static void shellsort(int[] array) {
        shellsort(array, 0, array.length - 1);
    }

    public static void shellsort(int[] array, int start, int end) {
        if (start < 0 || end < 0 || start > end || end > array.length - 1) {
            throw new IllegalArgumentException("Array index out of bounds");
        }
        int gap = 1;
        int len = end - start + 1;
        // Generate Knuth sequence 1, 4, 13, 40, 121, 364,1093, 3280, 9841 ...
        while (gap < len) gap = 3 * gap + 1;
        while (gap > 0) {
            int begin = start + gap;
            for (int i = begin; i <= end; i++) {
                int temp = array[i];
                int j = i;
                while (j >= begin && temp <= array[j - gap]) {
                    array[j] = array[j - gap];
                    j -= gap;
                }
                array[j] = temp;
            }
            gap /= 3;
        }
    }

    // Shell sort
    public static <T extends Comparable<? super T>> void shellsort(T[] array) {
        shellsort(array, 0, array.length - 1);
    }

    // Shell sort
    public static <T extends Comparable<? super T>> void shellsort(T[] array, int start, int end) {
        if (start < 0 || end < 0 || start > end || end > array.length - 1) {
            throw new IllegalArgumentException("Array index out of bounds");
        }
        int gap = 1;
        int len = end - start + 1;
        // Generate Knuth sequence 1, 4, 13, 40, 121, 364,1093, 3280, 9841 ...
        while (gap < len) gap = 3 * gap + 1;
        while (gap > 0) {
            int begin = start + gap;
            for (int i = begin; i <= end; i++) {
                T temp = array[i];
                int j = i;
                while (j >= begin && temp.compareTo(array[j - gap]) <= 0) {
                    array[j] = array[j - gap];
                    j -= gap;
                }
                array[j] = temp;
            }
            gap /= 3;
        }
    }

    public static byte[] subArray(byte[] src, int offset, int len) {
        if (offset == 0 && len == src.length) {
            return src;
        }
        if ((offset < 0 || offset >= src.length) || (offset + len > src.length)) {
            throw new IllegalArgumentException("Copy range out of array bounds");
        }
        byte[] dest = new byte[len];
        System.arraycopy(src, offset, dest, 0, len);

        return dest;
    }

    private static final void swap(int[] array, int a, int b) {
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }

    private static final <T> void swap(T[] array, int a, int b) {
        T temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }

    public static float[] to16BitFloatArray(byte[] data, boolean bigEndian) {
        short[] shorts = (short[]) toNBits(16, data, Integer.MAX_VALUE, bigEndian);
        float[] floats = new float[shorts.length];

        for (int i = 0; i < floats.length; i++) {
            floats[i] = toFloat(shorts[i]);
        }

        return floats;
    }

    /*
     * Tries to convert 24 bit floating point sample to 32 bit float data.
     * Up to now, there has been no way to do it correctly and there might be no
     * correct way to do this because 24 bit is not an IEEE floating point type.
     * 24 bit floating point images appear too dark using this conversion.
     */
    public static float[] to24BitFloatArray(byte[] data, boolean bigEndian) {
        int[] ints = (int[]) toNBits(24, data, Integer.MAX_VALUE, bigEndian);
        float[] floats = new float[ints.length];

        for (int i = 0; i < floats.length; i++) {
            /**
             int bits = ints[i]<<8;
             int sign     = ((bits & 0x80000000) == 0) ? 1 : -1;
             int exponent = ((bits & 0x7f800000) >> 23);
             int mantissa =  (bits & 0x007fffff);

             mantissa |= 0x00800000;

             floats[i] = (float)(sign * mantissa * Math.pow(2, exponent-150));
             */
            floats[i] = Float.intBitsToFloat(ints[i] << 8);
        }

        return floats;
    }

    // Convert byte array to long array, then to integer array discarding the higher bits
    public static int[] to32BitsLongArray(byte[] data, boolean bigEndian) {
        ByteBuffer byteBuffer = ByteBuffer.wrap(data);

        if (bigEndian) {
            byteBuffer.order(ByteOrder.BIG_ENDIAN);
        } else {
            byteBuffer.order(ByteOrder.LITTLE_ENDIAN);
        }

        LongBuffer longBuf = byteBuffer.asLongBuffer();
        long[] array = new long[longBuf.remaining()];
        longBuf.get(array);

        int[] iArray = new int[array.length];

        int i = 0;

        for (long l : array) {
            iArray[i++] = (int) l;
        }

        return iArray;
    }

    public static byte[] toByteArray(int value) {
        return new byte[]{
                (byte) value,
                (byte) (value >>> 8),
                (byte) (value >>> 16),
                (byte) (value >>> 24)
        };
    }

    public static byte[] toByteArray(int[] data, boolean bigEndian) {

        ByteBuffer byteBuffer = ByteBuffer.allocate(data.length * 4);

        if (bigEndian) {
            byteBuffer.order(ByteOrder.BIG_ENDIAN);
        } else {
            byteBuffer.order(ByteOrder.LITTLE_ENDIAN);
        }

        IntBuffer intBuffer = byteBuffer.asIntBuffer();
        intBuffer.put(data);

        byte[] array = byteBuffer.array();

        return array;
    }

    public static byte[] toByteArray(long[] data, boolean bigEndian) {

        ByteBuffer byteBuffer = ByteBuffer.allocate(data.length * 8);

        if (bigEndian) {
            byteBuffer.order(ByteOrder.BIG_ENDIAN);
        } else {
            byteBuffer.order(ByteOrder.LITTLE_ENDIAN);
        }

        LongBuffer longBuffer = byteBuffer.asLongBuffer();
        longBuffer.put(data);

        byte[] array = byteBuffer.array();

        return array;
    }

    public static byte[] toByteArray(short value) {
        return new byte[]{
                (byte) value, (byte) (value >>> 8)};
    }

    public static byte[] toByteArray(short[] data, boolean bigEndian) {

        ByteBuffer byteBuffer = ByteBuffer.allocate(data.length * 2);

        if (bigEndian) {
            byteBuffer.order(ByteOrder.BIG_ENDIAN);
        } else {
            byteBuffer.order(ByteOrder.LITTLE_ENDIAN);
        }

        ShortBuffer shortBuffer = byteBuffer.asShortBuffer();
        shortBuffer.put(data);

        byte[] array = byteBuffer.array();

        return array;
    }

    public static byte[] toByteArrayMM(int value) {
        return new byte[]{
                (byte) (value >>> 24),
                (byte) (value >>> 16),
                (byte) (value >>> 8),
                (byte) value};
    }

    public static byte[] toByteArrayMM(short value) {
        return new byte[]{
                (byte) (value >>> 8), (byte) value};
    }

    public static double[] toDoubleArray(byte[] data, boolean bigEndian) {
        return toDoubleArray(data, 0, data.length, bigEndian);
    }

    public static double[] toDoubleArray(byte[] data, int offset, int len, boolean bigEndian) {

        ByteBuffer byteBuffer = ByteBuffer.wrap(data, offset, len);

        if (bigEndian) {
            byteBuffer.order(ByteOrder.BIG_ENDIAN);
        } else {
            byteBuffer.order(ByteOrder.LITTLE_ENDIAN);
        }

        DoubleBuffer doubleBuf = byteBuffer.asDoubleBuffer();
        double[] array = new double[doubleBuf.remaining()];
        doubleBuf.get(array);

        return array;
    }

    // From http://stackoverflow.com/questions/6162651/half-precision-floating-point-in-java
    // Converts integer to float ignores the higher 16 bits
    public static float toFloat(int lbits) {
        // ignores the higher 16 bits
        int mant = lbits & 0x03ff;            // 10 bits mantissa
        int exp = lbits & 0x7c00;             // 5 bits exponent

        if (exp == 0x7c00) {                  // NaN/Inf
            exp = 0x3fc00;                    // -> NaN/Inf
        } else if (exp != 0) {                 // normalized value
            exp += 0x1c000;                   // exp - 15 + 127
            if (mant == 0 && exp > 0x1c400)   // smooth transition
            {
                return Float.intBitsToFloat(
                        (lbits & 0x8000) << 16
                                | exp << 13 | 0x3ff);
            }
        } else if (mant != 0) {                // && exp==0 -> subnormal
            exp = 0x1c400;                    // make it normal
            do {
                mant <<= 1;                   // mantissa * 2
                exp -= 0x400;                 // decrease exp by 1
            } while ((mant & 0x400) == 0);     // while not normal
            mant &= 0x3ff;                    // discard subnormal bit
        }                                     // else +/-0 -> +/-0

        return Float.intBitsToFloat(          // combine all parts
                                              (lbits & 0x8000) << 16          // sign  << ( 31 - 15 )
                                                      | (exp | mant) << 13);         // value << ( 23 - 10 )
    }

    public static float[] toFloatArray(byte[] data, boolean bigEndian) {
        return toFloatArray(data, 0, data.length, bigEndian);
    }

    public static float[] toFloatArray(byte[] data, int offset, int len, boolean bigEndian) {

        ByteBuffer byteBuffer = ByteBuffer.wrap(data, offset, len);

        if (bigEndian) {
            byteBuffer.order(ByteOrder.BIG_ENDIAN);
        } else {
            byteBuffer.order(ByteOrder.LITTLE_ENDIAN);
        }

        FloatBuffer floatBuf = byteBuffer.asFloatBuffer();
        float[] array = new float[floatBuf.remaining()];
        floatBuf.get(array);

        return array;
    }

    public static int[] toIntArray(byte[] data, boolean bigEndian) {
        return toIntArray(data, 0, data.length, bigEndian);
    }

    public static int[] toIntArray(byte[] data, int offset, int len, boolean bigEndian) {

        ByteBuffer byteBuffer = ByteBuffer.wrap(data, offset, len);

        if (bigEndian) {
            byteBuffer.order(ByteOrder.BIG_ENDIAN);
        } else {
            byteBuffer.order(ByteOrder.LITTLE_ENDIAN);
        }

        IntBuffer intBuf = byteBuffer.asIntBuffer();
        int[] array = new int[intBuf.remaining()];
        intBuf.get(array);

        return array;
    }

    public static long[] toLongArray(byte[] data, boolean bigEndian) {
        return toLongArray(data, 0, data.length, bigEndian);
    }

    public static long[] toLongArray(byte[] data, int offset, int len, boolean bigEndian) {

        ByteBuffer byteBuffer = ByteBuffer.wrap(data, offset, len);

        if (bigEndian) {
            byteBuffer.order(ByteOrder.BIG_ENDIAN);
        } else {
            byteBuffer.order(ByteOrder.LITTLE_ENDIAN);
        }

        LongBuffer longBuf = byteBuffer.asLongBuffer();
        long[] array = new long[longBuf.remaining()];
        longBuf.get(array);

        return array;
    }

    /**
     * Converts an input byte array to nBits data array using the smallest data type which
     * can hold the nBits data. Each data type contains only one data element.
     *
     * @param nBits     number of bits for the data element
     * @param input     the input array for the data elements
     * @param stride    scan line stride used to discard remaining bits
     * @param bigEndian the packing order of the bits. True if bigEndian, otherwise false.
     * @return an array of the smallest data type which can hold the nBits data
     */
    public static Object toNBits(int nBits, byte[] input, int stride, boolean bigEndian) {
        int value = 0;
        int bits_remain = 0;
        int temp_byte = 0;

        byte[] byteOutput = null;
        short[] shortOutput = null;
        int[] intOutput = null;
        Object output = null;

        int outLen = (int) ((input.length * 8L + nBits - 1) / nBits);

        if (nBits <= 8) {
            byteOutput = new byte[outLen];
            output = byteOutput;
        } else if (nBits <= 16) {
            shortOutput = new short[outLen];
            output = shortOutput;
        } else if (nBits <= 32) {
            intOutput = new int[outLen];
            output = intOutput;
        } else {
            throw new IllegalArgumentException("nBits exceeds limit - maximum 32");
        }

        int offset = 0;
        int index = 0;

        int strideCounter = 0;

        loop:
        while (true) {

            if (!bigEndian) {
                value = (temp_byte >> (8 - bits_remain));
            } else {
                value = (temp_byte & MASK[bits_remain]);
            }

            while (nBits > bits_remain) {
                if (offset >= input.length) {
                    break loop;
                }

                temp_byte = input[offset++] & 0xff;

                if (bigEndian) {
                    value = ((value << 8) | temp_byte);
                } else {
                    value |= (temp_byte << bits_remain);
                }

                bits_remain += 8;
            }

            bits_remain -= nBits;

            if (bigEndian) {
                value = (value >> (bits_remain));
            }

            value &= MASK[nBits];

            if (++strideCounter % stride == 0) {
                bits_remain = 0; // Discard the remaining bits
            }

            if (nBits <= 8) {
                byteOutput[index++] = (byte) value;
            } else if (nBits <= 16) {
                shortOutput[index++] = (short) value;
            } else {
                intOutput[index++] = value;
            }
        }

        return output;
    }

    public static double[] toPrimitive(Double[] doubles) {
        double[] dArray = new double[doubles.length];
        int i = 0;

        for (double d : doubles) {
            dArray[i++] = d;
        }

        return dArray;
    }

    public static float[] toPrimitive(Float[] floats) {
        float[] fArray = new float[floats.length];
        int i = 0;

        for (float f : floats) {
            fArray[i++] = f;
        }

        return fArray;
    }

    public static int[] toPrimitive(Integer[] integers) {
        int[] ints = new int[integers.length];
        int i = 0;

        for (int n : integers) {
            ints[i++] = n;
        }

        return ints;
    }

    public static long[] toPrimitive(Long[] longs) {
        long[] lArray = new long[longs.length];
        int i = 0;

        for (long l : longs) {
            lArray[i++] = l;
        }

        return lArray;
    }

    public static short[] toPrimitive(Short[] shorts) {
        short[] sArray = new short[shorts.length];
        int i = 0;

        for (short s : shorts) {
            sArray[i++] = s;
        }

        return sArray;
    }

    public static short[] toShortArray(byte[] data, boolean bigEndian) {
        return toShortArray(data, 0, data.length, bigEndian);
    }

    public static short[] toShortArray(byte[] data, int offset, int len, boolean bigEndian) {

        ByteBuffer byteBuffer = ByteBuffer.wrap(data, offset, len);

        if (bigEndian) {
            byteBuffer.order(ByteOrder.BIG_ENDIAN);
        } else {
            byteBuffer.order(ByteOrder.LITTLE_ENDIAN);
        }

        ShortBuffer shortBuf = byteBuffer.asShortBuffer();
        short[] array = new short[shortBuf.remaining()];
        shortBuf.get(array);

        return array;
    }

    /**
     * 返回随机且不重复数组
     */
    public static int[] getRandomArrays(int length) {
        int[] a1 = new int[length];

        for (int i = 0; i < a1.length; i++) {
            a1[i] = i;
        }

        return getRandomArrays(a1);
    }

    /**
     * 打乱数组元素存储顺序
     */
    public static int[] getRandomArrays(int[] a1) {
        int[] ret = new int[a1.length];
        List<Integer> collect = Arrays.stream(a1).boxed().collect(Collectors.toList());

        for (int i = 0; i < ret.length; i++) {
            ret[i] = getRandomItemAnRemove(collect);
        }
        return ret;
    }

    private static <T> T getRandomItemAnRemove(List<T> list) {
        if (list == null || list.isEmpty()) {
            return null;
        }
        return list.remove(new Random().nextInt(list.size()));
    }

    /**
     * 随机位移元素位置
     *
     * @param array 数组
     * @param count 位移次数
     */
    public static void random(int[] arr, int count) {
        for (int i = 0; i < count + 1; i++) {
            int a = 0, b = 0;
            while (a == b) {
                a = new Random().nextInt(arr.length);
                b = new Random().nextInt(arr.length);
            }
            int t = arr[a];
            arr[a] = arr[b];
            arr[b] = t;
        }
    }
}
